// 版权归Go作者所有。版权所有。
// 此源代码的使用受BSD样式的约束
// 可以在许可证文件中找到的许可证。

package ssa

import (
	"cmd/internal/src"
)

// findlive返回f中的可访问块和活动值。
// 调用方在处理完f.retDeadcodeLive（live）后应调用它。
func findlive(f *Func) (reachable []bool, live []bool) {
	reachable = ReachableBlocks(f)
	var order []*Value
	live, order = liveValues(f, reachable)
	f.retDeadcodeLiveOrderStmts(order)
	return
}

// ReachableBlocks返回f中的可到达块。
func ReachableBlocks(f *Func) []bool {
	reachable := make([]bool, f.NumBlocks())
	reachable[f.Entry.ID] = true
	p := make([]*Block, 0, 64) // 堆栈式工作列表
	p = append(p, f.Entry)
	for len(p) > 0 {
		// 弹出一个可到达的块
		b := p[len(p)-1]
		p = p[:len(p)-1]
		// 将继任者标记为可到达
		s := b.Succs
		if b.Kind == BlockFirst {
			s = s[:1]
		}
		for _, e := range s {
			c := e.b
			if int(c.ID) >= len(reachable) {
				f.Fatalf("block %s >= f.NumBlocks()=%d?", c, len(reachable))
			}
			if !reachable[c.ID] {
				reachable[c.ID] = true
				p = append(p, c) // 推
			}
		}
	}
	return reachable
}

// liveValues返回f中的活动值和符合条件的值列表
// 以相反的数据流顺序显示待处理语句。
// 第二个结果用于帮助保留用于调试的语句边界。
// 可访问是从块ID到块是否可访问的映射。
// 调用方应调用f.retDeadcodeLive（live）和f.retDeadcodeLiveOrderStmts（liveOrderStmts）
// 当它们处理完返回值时。
func liveValues(f *Func, reachable []bool) (live []bool, liveOrderStmts []*Value) {
	live = f.newDeadcodeLive()
	if cap(live) < f.NumValues() {
		live = make([]bool, f.NumValues())
	} else {
		live = live[:f.NumValues()]
		for i := range live {
			live[i] = false
		}
	}

	liveOrderStmts = f.newDeadcodeLiveOrderStmts()
	liveOrderStmts = liveOrderStmts[:0]

	// 在ReLogalc之后，考虑所有的值是活的。
	// 有关详细信息，请参见regalloc.go顶部和deadcode中的注释。
	if f.RegAlloc != nil {
		for i := range live {
			live[i] = true
		}
		return
	}

	// 记录我们需要的所有内联索引
	var liveInlIdx map[int]bool
	pt := f.Config.ctxt.PosTable
	for _, b := range f.Blocks {
		for _, v := range b.Values {
			i := pt.Pos(v.Pos).Base().InliningIndex()
			if i < 0 {
				continue
			}
			if liveInlIdx == nil {
				liveInlIdx = map[int]bool{}
			}
			liveInlIdx[i] = true
		}
		i := pt.Pos(b.Pos).Base().InliningIndex()
		if i < 0 {
			continue
		}
		if liveInlIdx == nil {
			liveInlIdx = map[int]bool{}
		}
		liveInlIdx[i] = true
	}

	// 查找所有活动值
	q := f.Cache.deadcode.q[:0]
	defer func() { f.Cache.deadcode.q = q }()

	// 起始集：可到达块的所有控制值都是活动的。
	// 调用是活动的（因为被调用方可以观察内存状态）。
	for _, b := range f.Blocks {
		if !reachable[b.ID] {
			continue
		}
		for _, v := range b.ControlValues() {
			if !live[v.ID] {
				live[v.ID] = true
				q = append(q, v)
				if v.Pos.IsStmt() != src.PosNotStmt {
					liveOrderStmts = append(liveOrderStmts, v)
				}
			}
		}
		for _, v := range b.Values {
			if (opcodeTable[v.Op].call || opcodeTable[v.Op].hasSideEffects) && !live[v.ID] {
				live[v.ID] = true
				q = append(q, v)
				if v.Pos.IsStmt() != src.PosNotStmt {
					liveOrderStmts = append(liveOrderStmts, v)
				}
			}
			if v.Type.IsVoid() && !live[v.ID] {
				// 唯一的无效操作是零检查和内联标记。我们必须保留这些。
				if v.Op == OpInlMark && !liveInlIdx[int(v.AuxInt)] {
					// 我们不需要为那些
					// 已经完全优化了。
					// TODO:仅为以下实体保存标记：
					// 有错误的指令或电话吗？
					continue
				}
				live[v.ID] = true
				q = append(q, v)
				if v.Pos.IsStmt() != src.PosNotStmt {
					liveOrderStmts = append(liveOrderStmts, v)
				}
			}
		}
	}

	// 计算活动值的传递闭包。
	for len(q) > 0 {
		// 弹出一个可到达的值
		v := q[len(q)-1]
		q = q[:len(q)-1]
		for i, x := range v.Args {
			if v.Op == OpPhi && !reachable[v.Block.Preds[i].b.ID] {
				continue
			}
			if !live[x.ID] {
				live[x.ID] = true
				q = append(q, x) // 推
				if x.Pos.IsStmt() != src.PosNotStmt {
					liveOrderStmts = append(liveOrderStmts, x)
				}
			}
		}
	}

	return
}

// deadcode从f中删除死代码。
func deadcode(f *Func) {
	// regalloc之后的死码现在是禁止的。帝王的
	// 不会产生合法的SSA，这将导致
	// 所需的移动被取消。请参阅网站上的评论
	// regalloc顶部。查看详细信息。
	if f.RegAlloc != nil {
		f.Fatalf("deadcode after regalloc")
	}

	// 找到可到达的块。
	reachable := ReachableBlocks(f)

	// 去除从死代码到活代码的边缘。
	for _, b := range f.Blocks {
		if reachable[b.ID] {
			continue
		}
		for i := 0; i < len(b.Succs); {
			e := b.Succs[i]
			if reachable[e.b.ID] {
				b.removeEdge(i)
			} else {
				i++
			}
		}
	}

	// 消除活代码中的死角。
	for _, b := range f.Blocks {
		if !reachable[b.ID] {
			continue
		}
		if b.Kind != BlockFirst {
			continue
		}
		b.removeEdge(1)
		b.Kind = BlockPlain
		b.Likely = BranchUnknown
	}

	// 剪接在清除死区时引入的任何副本。
	copyelim(f)

	// 找到活的价值。
	live, order := liveValues(f, reachable)
	defer f.retDeadcodeLive(live)
	defer f.retDeadcodeLiveOrderStmts(order)

	// 从namedValues映射中删除无效项和重复项。
	s := f.newSparseSet(f.NumValues())
	defer f.retSparseSet(s)
	i := 0
	for _, name := range f.Names {
		j := 0
		s.clear()
		values := f.NamedValues[*name]
		for _, v := range values {
			if live[v.ID] && !s.contains(v.ID) {
				values[j] = v
				j++
				s.add(v.ID)
			}
		}
		if j == 0 {
			delete(f.NamedValues, *name)
		} else {
			f.Names[i] = name
			i++
			for k := len(values) - 1; k >= j; k-- {
				values[k] = nil
			}
			f.NamedValues[*name] = values[:j]
		}
	}
	clearNames := f.Names[i:]
	for j := range clearNames {
		clearNames[j] = nil
	}
	f.Names = f.Names[:i]

	pendingLines := f.cachedLineStarts // 保存需要移动到新值/块的语句边界
	pendingLines.clear()

	// 取消值链接并保留语句边界
	for i, b := range f.Blocks {
		if !reachable[b.ID] {
			// TODO如果控件是语句边界怎么办？太晚了。
			b.ResetControls()
		}
		for _, v := range b.Values {
			if !live[v.ID] {
				v.resetArgs()
				if v.Pos.IsStmt() == src.PosIsStmt && reachable[b.ID] {
					pendingLines.set(v.Pos, int32(i)) // TODO可以是一条生产线的多个pos
				}
			}
		}
	}

	// 为丢失的行寻找新的归宿——要求数据流中最早的行也在同一块中
	for i := len(order) - 1; i >= 0; i-- {
		w := order[i]
		if j := pendingLines.get(w.Pos); j > -1 && f.Blocks[j] == w.Block {
			w.Pos = w.Pos.WithIsStmt()
			pendingLines.remove(w.Pos)
		}
	}

	// 任何与活动值不匹配的边界都可以移动到块端点
	pendingLines.foreachEntry(func(j int32, l uint, bi int32) {
		b := f.Blocks[bi]
		if b.Pos.Line() == l && b.Pos.FileIndex() == j {
			b.Pos = b.Pos.WithIsStmt()
		}
	})

	// 从块的值列表中删除无效值。死而复生
	// 将值分配给分配器。
	for _, b := range f.Blocks {
		i := 0
		for _, v := range b.Values {
			if live[v.ID] {
				b.Values[i] = v
				i++
			} else {
				f.freeValue(v)
			}
		}
		b.truncateValues(i)
	}

	// 从WBLoads列表中删除死块。
	i = 0
	for _, b := range f.WBLoads {
		if reachable[b.ID] {
			f.WBLoads[i] = b
			i++
		}
	}
	clearWBLoads := f.WBLoads[i:]
	for j := range clearWBLoads {
		clearWBLoads[j] = nil
	}
	f.WBLoads = f.WBLoads[:i]

	// 删除无法访问的块。将死块返回给分配器。
	i = 0
	for _, b := range f.Blocks {
		if reachable[b.ID] {
			f.Blocks[i] = b
			i++
		} else {
			if len(b.Values) > 0 {
				b.Fatalf("live values in unreachable block %v: %v", b, b.Values)
			}
			f.freeBlock(b)
		}
	}
	// 零余数有助于GC
	tail := f.Blocks[i:]
	for j := range tail {
		tail[j] = nil
	}
	f.Blocks = f.Blocks[:i]
}

// removeEdge从b（和）中移除第i个输出边
// b.Succs[i].b）中相应的传入边。
func (b *Block) removeEdge(i int) {
	e := b.Succs[i]
	c := e.b
	j := e.i

	// 调整b.成功
	b.removeSucc(i)

	// 调整c.Preds
	c.removePred(j)

	// 从c的phi中删除phi参数。
	n := len(c.Preds)
	for _, v := range c.Values {
		if v.Op != OpPhi {
			continue
		}
		v.Args[j].Uses--
		v.Args[j] = v.Args[n]
		v.Args[n] = nil
		v.Args = v.Args[:n]
		phielimValue(v)
		// 注意：这比看起来更复杂。替换
		// 带有副本的Phi通常会导致问题，因为
		// Phi和Copy的语义并不完全相同。
		// Phi参数总是来自前置块，
		// 而副本则不然。这在循环中很重要，例如：
		// 1:x=（φy）
		// y=（加上x1）
		// 转到1
		// 如果我们替换Phi->Copy，我们得到
		// 1:x=（复制y）
		// y=（加上x1）
		// 转到1
		// （φy）指y的*先前*值，而
		// （复制y）指y的*当前*值。
		// 修改后的代码有一个周期和调度程序
		// 我会吐出来的。
		// None
		// 幸运的是，这种情况只会发生在死人身上
		// 代码循环。我们知道我们使用的代码是
		// 没有死，所以我们没事。
		// 证据：如果我们有一个潜在的坏循环，我们有一个
		// 这种情况：
		// x=（φz）
		// y=（op1 x…）
		// z=（op2y…）
		// 其中opX不是Phi ops。但这种情况
		// 表示支配图中的循环。在
		// 例如，x.块支配y.块，y.块支配
		// z、 块，z块主导x块（治疗）
		// “支配”是反身的）。支配者中的循环
		// 图形只能在无法到达的循环中发生。
	}
}
